package leetcode.hot100;

import datastruct.tree.TreeNode;
import datastruct.tree.Utils;

public class Solution124 {

    public static void main(String[] args) {
        TreeNode root = Utils.deserialize("1,2,null,null,3,null,null");
        Solution124 s = new Solution124();
        System.out.println(s.maxPathSum(root));
    }


    public int maxPathSum(TreeNode root) {
        return maxLengthAndPath(root)[1];
    }

    public int[] maxLengthAndPath(TreeNode root){
        //返回本树路径中从根开始的最长length，以及所有路径中最长的max
        if(root==null) return new int[]{Integer.MIN_VALUE,Integer.MIN_VALUE};
        int[] left = maxLengthAndPath(root.left);
        int[] right = maxLengthAndPath(root.right);
        int legMax = Math.max(left[0],right[0]);
        int legMin = Math.min(left[0],right[0]);
        //根到子最长的length = root值 + 左右子树最长的从根开始中最大者
        int length = root.val + Math.max(0,legMax);
        //root为根的树中所有路径中最长的max = （左右子树最长路径，root值+左腿，root值+右腿，root值，root值+左右腿）中最大者
        int childPathMax = Math.max(left[1],right[1]);
        //加不加左右腿？要看左右腿对本节点的最大路径有无贡献
        int rootPathMax = root.val;
        rootPathMax += Math.max(0,legMax);
        rootPathMax += Math.max(0,legMin);
        int max = Math.max(childPathMax,rootPathMax);
        return new int[]{length,max};
    }
}
